class Solution:
    def wordBreak(self, s: str, wordDict):
        if not wordDict:
            return []
        from collections import defaultdict
        self.d = defaultdict(str)
        wordDict = set(wordDict) # 加了这一句后直接变36ms, beat 94.33% !!! 因为list的查询是O(1), 而set和dict的查询是O(1)!!!
        def solve(s, dic, start, l):
            if start in self.d:
                return self.d[start]
            tmp = []
            if start==l:
                tmp.append('')
            for i in range(start+1, l+1):
                if s[start:i] in dic:
                    lt = solve(s, dic, i, l)
                    for item in lt:
                        concat = s[start:i]+' '+item if item!='' else s[start:i]
                        tmp.append(concat)
            self.d[start] = tmp
            return tmp

        return solve(s, wordDict, 0, len(s))


if __name__ == '__main__':
    so = Solution()
    # s = "catsanddog"
    # wordDict = ["cat", "cats", "and", "sand", "dog"]
    # s = "ab"
    # wordDict = ["a", "b"]

    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "b"]

    re = so.wordBreak(s, wordDict)
    print(re)
